package com.example.algorithm.greedy;

import java.util.Arrays;

/**
 *  字符串 x 可以打破字符串 y （两者长度都为 n ）需满足对于所有 i（在 0 到 n - 1 之间）都有 x[i] >= y[i]（字典序意义下的顺序）。
 *  示例 1：
 *  输入：s1 = "abc", s2 = "xya"
 * 输出：true
 * 解释："ayx" 是 s2="xya" 的一个排列，"abc" 是字符串 s1="abc" 的一个排列，且 "ayx" 可以打破 "abc" 。
 *  示例 2：
 *  输入：s1 = "abe", s2 = "acd"
 * 输出：false
 * 解释：s1="abe" 的所有排列包括："abe"，"aeb"，"bae"，"bea"，"eab" 和 "eba" ，s2="acd" 的所有排列包括：
 * "acd"，"adc"，"cad"，"cda"，"dac" 和 "dca"。然而没有任何 s1 的排列可以打破 s2 的排列。也没有 s2 的排列能打破 s1 的排列。
 */
public class Leetcode1433_CheckIfCanBreak {
    public static void main(String[] args) {
        System.out.println(checkIfCanBreak("bxfowqvnrhuzwqohquamvszkvunb", "xjegbjccjjxfnsiearbsgsofywtq"));
    }

    /**
     * 解法一：通过字符排序，将两个字符串 的最小排列形式找出来
     * 如果s1的最小 大于 s2的最小，那么s1可以打破s2
     * 如果不能，看卡s2能否打破s1
     * 如果均不能则返回false
     * @param s1
     * @param s2
     * @return
     */
    public static boolean checkIfCanBreak(String s1, String s2) {
        char[] chars1 = s1.toCharArray();
        char[] chars2 = s2.toCharArray();
        Arrays.toString(chars1);
        Arrays.sort(chars1);
        Arrays.sort(chars2);

        int count = 0;

        // 检查字符串1是否打破字符串2
        while (count < chars1.length && chars1[count] >= chars2[count]) {
            count++;
        }
        if (count == chars1.length)
            return true;

        // 检查字符串2是否打破字符串1
        count = 0;
        while (count < chars2.length && chars2[count] >= chars1[count]) {
            count++;
        }
        if (count == chars1.length)
            return true;

        return false;
    }
}
